/**
 * 剑指 Offer 40. 最小的k个数
 * https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/
 */
const { displayBaseArray } = require('../../libs/public');

/**
 * @param {number[]} arr
 * @param {number} a
 * @param {number} b
 */
function swap(arr, a, b) {
  const temp = arr[a];
  arr[a] = arr[b];
  arr[b] = temp;
}

/**
 * @param {number[]} arr
 * @param {number} length
 */
function resolveHeap(arr, length) {
  for (let parent = Math.floor(length / 2) - 1; parent >= 0; parent -= 1) {
    const parentVal = arr[parent];
    const childLeft = parent * 2 + 1;
    const childLeftVal = arr[childLeft];
    const childRight = childLeft + 1;
    const childRightVal = childRight >= length ? Infinity : arr[childRight];
    if (parentVal <= childLeftVal && parentVal <= childRightVal) {
      continue;
    }
    if (childLeftVal < childRightVal) {
      swap(arr, parent, childLeft);
    } else {
      swap(arr, parent, childRight);
    }
  }
}

/**
 * @param {number[]} arr
 * @param {number} k
 * @return {number[]}
 */
function getLeastNumbers(arr, k) {
  let { length } = arr;
  const result = new Array(k);
  for (let i = 0; i < k; i += 1) {
    resolveHeap(arr, length);
    [result[i]] = arr;
    swap(arr, 0, length - 1);
    length -= 1;
  }
  return result;
}

console.log(displayBaseArray(getLeastNumbers([3, 2, 1], 2)) === '[1,2]');
console.log(displayBaseArray(getLeastNumbers([0, 1, 2, 1], 1)) === '[0]');
